package leetcode.dynamic_programming;

/**
 * @author mgl
 * @version 1.0
 * @description 路径数量，但是有障碍 leetcode第63题
 * @date 2023/10/5 12:24
 */
public class UniquePathsWithObstacles {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int row = obstacleGrid.length;
        int column = obstacleGrid[0].length;

        int[][] arr = new int[row][column];
        arr[0][0] = 1; //从最开始的一个格子是  1种方法
        if(obstacleGrid[0][0] == 1) return 0; //如果最开始的位置有障碍，直接返回，不能通过
        for (int i = 0; i < column; i++) {
            for (int j = 0; j < row; j++) {
                if (obstacleGrid[j][i] == 1) continue;

                if (j - 1 >= 0 && i - 1 >= 0) { // 上面和左面都不为空，如果不是障碍，路径数为这两个之和
                    if (obstacleGrid[j - 1][i] == 0) arr[j][i] += arr[j - 1][i];
                    if (obstacleGrid[j][i - 1] == 0) arr[j][i] += arr[j][i - 1];
                } else if (j - 1 >= 0) {
                    if (obstacleGrid[j - 1][i] == 0) arr[j][i] = arr[j - 1][i]; //上面不为空，如果上面不是障碍，路径数直接等于上面的
                } else if (i - 1 >= 0) {
                    if (obstacleGrid[j][i - 1] == 0) arr[j][i] = arr[j][i - 1]; //左面不为空，如果左边不是障碍，路径数直接等于左面的
                }
            }
        }

        return arr[row - 1][column - 1];

    }

    public static void main(String[] args) {
//        int[][] arr = new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        int[][] arr = new int[][]{{0, 1}, {0, 0}};
        System.out.println(new UniquePathsWithObstacles().uniquePathsWithObstacles(
                arr
        ));
    }
}
